https://www.acmicpc.net/problem/2747

피보나치 수열에서 n번째 수를 구하는 문제

재귀적인 방법을 사용하면 2의 n제곱으로 엄청난 시간복잡도를 가지게 됨

내가 쓴 답변

n = int(input())

def fibo(num):
    cache = [0 for _ in range(num + 1)]
    cache[0] = 0
    cache[1] = 1

    for i in range(2, num + 1):
        cache[i] = cache[i - 1] + cache[i - 2]
    return cache[num]

print(fibo(n))

다른 답변

n = int(input())
a, b = 0, 1
while n > 0:
    a, b = b, a + b
    n -= 1
print(a)